package com.ma.DataStruct;

import java.time.OffsetDateTime;

/**
 * @param <Key> 任何一种可比较大小的数据类型
 *              <p>
 *              ！！！数组索引
 */
public class MaxPQ<Key extends Comparable<Key>> {

    //存储元素的数组
    private Key[] pq;
    //当前队列的元素个数
    private int N = 0;

    int parent(int root) {
        // 父节点的索引
        return root / 2;
    }

    // 左孩子的索引
    int left(int root) {
        return root * 2;
    }

    // 右孩子的索引
    int right(int root) {
        return root * 2 + 1;
    }

    /*  返回当前队列最大元素 */
    public MaxPQ(int cap) {
        //索引0不用，所以多分配一个空间
        pq = (Key[]) new Comparable[cap + 1];
    }

    public Key max() {
        return pq[1];
    }

    /* 插入元素key */
    public void insert(Key key) {
        N++;
        pq[N] = key;
        swim(N);

    }

    /* 删除并返回当前队列的最大元素 */
    public Key delMax() {
        Key max = pq[1];
        exch(1, N);
        pq[N] = null;
        sink(1);
        return max;
    }

    /* 上浮第 k 个元素（k是索引！） 以维护最大堆的性质 */
    public void swim(int k) {
        // k=1 已经在堆顶，无法上浮
        while (k > 1 && less(parent(k), k)) {
            //如果k比父节点大，上浮
            //交换两者
            exch(parent(k), k);
            k = parent(k);
        }

    }

    /* 下沉第k个元素 以维护最大堆的性质 */
    public void sink(int k) {
        //已经在堆底无需sink
        while (left(k) <= N) {
            //假设左节点为最大子节点
            int older = left(k);
            //若右节点存在并且比左节点大，右节点为最大字节点
            if (right(k) <= N && less(older, right(k))) {
                older = right(k);
            }
            //父节点比最大字节点大，无需下沉
            if (less(older, k)) {
                break;
            }
            //交换父子
            exch(older, k);
            k = older;
        }

    }

    /* 交换数组两个元素 */
    public void exch(int i, int j) {
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    /* pq[i]是否比pq[j]小？*/
    public boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }


}
